





<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 16, Exercise 7<BR>

<BR>

</H1>



We define a new data member <code class=code>iMax</code>

for the class

<code class=code>MaxLoading</code>.

This gives the largest

<code class=code>i</code> for which we have to save the

<code class=code>x[i]</code> value.

Whenever we find a better solution,

<code class=code>iMax</code>

is reset to <code class=code>n</code> indicating

<code class=code>x[1:n]</code> are to be saved.

When we backup from a node, we first determine if the

<code class=code>x[i]</code> value is to be saved.

If it is to be saved, then the value of

<code class=code>iMax</code> is decresed by 1.

<br><br>

The new code is given below and in the files

<code class=code>bloadf.*</code>.



<HR class = coderule>

<pre class = code>

template&lt;class T&gt;

class Loading {

   friend MaxLoading(T [], T, int, int []);

   private:

      void maxLoading(int i);

      int n,      // number of containers

          *x,     // current solution

          *bestx; // best solution so far

      T *w,       // container weight array

        c,        // ship capacity

        cw,       // weight of current loading

        bestw,    // weight of best loading so far

        r,        // sum of remaining container weights

        iMax;     // incremental saving of

                  // bestx[1:i] yet to be done

};



template&lt;class T&gt;

void Loading&lt;T&gt;::maxLoading(int i)

{// Search from level i node.

   if (i &gt; n) {// at a leaf

      // need to save all values

      iMax = n;

      bestw = cw;

      return;}



   // check subtrees

   r -= w[i];

   if (cw + w[i] &lt;= c) {// try x[i] = 1

      x[i] = 1;

      cw += w[i];

      maxLoading(i+1);

      if (iMax == i) {// must save x[i]

         bestx[i] = 1;

         iMax--;

         }

      cw -= w[i];

      }

   if (cw + r &gt; bestw) {// try x[i] = 0

      x[i] = 0;

      maxLoading(i+1);

      if (iMax == i) {// must save x[i]

         bestx[i] = 0;

         iMax--;

         }

      }

   r += w[i];

}



template&lt;class T&gt;

T MaxLoading(T w[], T c, int n, int bestx[])

{// Return best loading and its value.

   Loading&lt;T&gt; X;

   // initialize X

   X.x = new int [n+1];

   X.w = w;

   X.c = c;

   X.n = n;

   X.bestx = bestx;

   X.bestw = 0;

   X.cw = 0;

   X.iMax = 0;

   // initial r is sum of all weights

   X.r = 0;

   for (int i = 1; i &lt;= n; i++) 

      X.r += w[i];

   X.maxLoading(1);

   delete [] X.x;

   return X.bestw;

}

<hr class=coderule>

</pre>



</FONT>

</BODY>

</HTML>

